package Lee_code;

import java.util.Arrays;

public class Lee_300_2 {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        //初始化
        Arrays.fill(dp, 1);
        // dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
        for (int i=1; i<len; i++){
            for (int j=0; j<i; j++){
                if (nums[i]>nums[j])
                    // 取dp[j] + 1的最大值
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        return dp[len-1];
    }
}
